/*
Insertion Sort List Total Accepted: 45895 Total Submissions: 173374 My Submissions Question Solution
Sort a linked list using insertion sort.
*/

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <fstream>
#include <sstream>
#include <unordered_set>
#include "print.h"
using namespace std;

/**
* Definition for binary tree*/


void testForStack()
{
	stack<int> mystack;
	mystack.push(10);
	mystack.push(20);
	mystack.top() -= 5;
	cout << "mystack.top() is now " << mystack.top() << endl;
}

void testForIntToString()
{
	int a = 10;
	stringstream ss;
	ss << a;
	string str = ss.str();
	cout << str << endl;

	string str1 = to_string(a);

}


class Solution {
public:
	ListNode* insertionSortList(ListNode* head) {
		if (head == NULL || head->next == NULL)
			return head;

		ListNode *head2 = head;
		head2 = head2->next;
		head->next = NULL;
		while (head2!=NULL)
		{
			ListNode *ptr1 = head;
			ListNode *pre = head;
			ListNode *cur = head2;
			head2 = head2->next;

			if (cur->val<=ptr1->val)
			{
				cur->next = ptr1;
				head = cur;
				continue;
			}
			while (ptr1!=NULL&&ptr1->val<cur->val)
			{
				pre = ptr1;
				ptr1 = ptr1->next;

			}

			if (ptr1==NULL)
			{
				pre->next = cur;
				cur->next = NULL;
			}
			else
			{
				pre->next = cur;
				cur->next = ptr1;
			}

			//if (true)
			
		}

		return head;
	}
};
int main(int argc, char* argv[])
{

	ListNode *head = new ListNode(1);
	ListNode *head1 = new ListNode(3);
	ListNode *head2 = new ListNode(2);
	ListNode *head3 = new ListNode(5);
	ListNode *head4 = new ListNode(4);

	head->next = head1;
	head1->next =head2;
	head2->next = head3;
	head3->next = head4;
	Solution s;
	head = s.insertionSortList(head);

	//result = s.partition(str);
	//stackTree.push(p->left);
	//stackTree.push(p->right);
	//if (s.isPalindrome(str1))
	//	cout << " True" << endl;
	//else
	//	cout << "false" << endl;
	system("pause");
	return 0;
}
//std::unordered_set<std::string> myset =
//{ "hot", "dot", "dog", "lot", "log" };

//std::cout << "myset contains:";
// for (auto it = myset.begin(); it != myset.end(); ++it)
//std::cout << " " << *it;
//;; std::cout << std::endl;

//TreeNode *root = new TreeNode(1);
//TreeNode *left = new TreeNode(2);
//TreeNode *right = new TreeNode(3);

//root->left = left;
//root->right = right;